Talk talk China

If state's support and Andy's energy do not wane, Andy Yao's institute in Beijing might become, over time, the next Weizmann: one of the best places for theory in the world, the first choice for Chinese nationals who complete their PhD in the US, and an attractive destination for non-Chinese for their post-doc/ sabbatical/ summer. Meanwhile, it is an exciting place to be, with a palpable sense that great things are going to happen. (And I don't remember if I have already mentioned that the food is good.)

As I anticipate many happy returns, I have been reading a bit about China, and I have enjoyed reading talk talk China. It is written by three expats, living in Beijing, China and Hong Kong. Some entries were written when one of them lived in Shanghai. It is mostly devoted to ranting about China, so many posts may be offensive to many people, but, through the ranting, they say very interesting things about China, about foreigners in China, and about the Chinese.

Their claim to fame is this post about the "lao wai death stare," which I experienced even in my very short stay. This , this, this, and this sound familiar too.

Apparently, it is very difficult for a foreigner, or even for a Chinese-born white person, to feel accepted. The comments on that post are particularly interesting, because many posters make a comparison with Taiwan and speculate on how things may change in China. (Or, in the rest of China, if you prefer.)

Indeed, when I arrived at the customs/immigration at Beijing airport, I felt something was strange with the signs pointing to the lines for "Chinese nationals" and for "Foreigners," and then I realized I had never seen the word "foreigner" anywhere else in this context. In Europe it's always "EU Nationals" and "Non-EU Nationals," in the US it is "US Citizens" and "Visitors" (even though, in the paperwork, I am an alien, which is about the worst term they could possibly choose) and so on. My impression is that a lot of this has to do with there being no notion of "politically correct speech" in China (yet). "I like foreigners, with their big noses and sunken eyes" someone told me in Beijing, presumably as a compliment. I am not saying it is a bad thing, I am not a big fan of PC-speech myself. (But this is a subject that would need its own post.)

I had the most fun reading this post about English names. (Warning: even the title of the post is offensive.) In Beijing I met a Beckham and a Gerrard (they are names of football players), and in Taipei I met a Bevis, but this is nothing compared to the examples given by the original poster and the commenters. Of course, now that I am considering "reckless card" as my Chinese name, the joke is on me.

The New York Times and geography

From an article on Michael Jackson in Japan:

Jackson arrived Friday night with his three children and will stay through Wednesday on the first leg of a swing through Asia that will include stops in Singapore, Shanghai, China and Hong Kong.

Hair, addresses, lockers and beer

A week after coming back, what is it about Taipei that has stuck in my memory?

Men's hairstyles, for sure. Indeed, every time I saw someone with his hair spiked sideways like a fan, I had to wonder: isn't he driving a scooter, like everybody else? And so, doesn't he have to wear a helmet? I still don't understand how they manage.

In most cities, an address is a simple two-dimensional thing: you give the name of the street and the number, like 742 Evergreen Terrace. Sometimes, a street may have a North side and a South side, or a East side and a West side. So you may have to say 129 West 81th Street.

In Taipei, this is just the start. Each major street, besides possibly having a North and a South (or East and West) side, is divided into sections, each section being about one or two miles. My hotel, for example, was off Zhongshan North Road, Section 2. Now, this is just the beginning. Side streets of main roads don't get a name, but rather a number, as if the street itself had a street address. So my hotel was on Zhongshan North Road, Section 2, Lane 11. Now you can add the number of your building and have your address. Unless, that is, you are in a side street of the side street. Such side-squared streets are called alleys (in the English standard translation). This, for example, is the name of such a street:

I want to stress once more: this is just the name of a street, not a complete address. It's like the sign near my place that says "18th."

Both at the museums and at the clubs that we went to, we found lockers instead of a coat check. It works very well, especially in clubs. It is safer, and there is no queue. It is a bit odd that a corner of a club would look like a gym, but you get used to it. I was reminded of my first entrance in a club in Beijing. The coat check had a long line (which was brazenly jumped by a person while I was waiting), at the end of which there was a short but wide woman in a tiny coat check room, completely surrounded by hanging clothes. She was wielding a sort of broomstick with a hook on it, that she used to hang clothes on hooks that were running all over the walls. She said something in Chinese to me when I gave her my jacket. Someone translated for me. "She says to look where she is putting your coat, so you can tell her where it is when you pick it up." Evidently, the number of my coat check ticket had no relation with the location where she hanged it.

The club that I liked in Taipei, besides the lockers, had good music and a nice vibe, as already reported. The cover charge entitled each of us to two drinks. When I asked for a beer, the barman gave me a warm beer. (It was Heineken, not Guiness.) When he saw my face when I started drinking, he helpfully offered a glass full of ice. I remembered reading about the warm beer on the web, but assuming it was just an urban legend, like the friendly shopclercks. And so I had two warm beers that night, and two more the following night. You can't let something free go to waste.

The following monday, I was taken to an "all you can drink" night. For a substantial cover charge (about US\$15) one could have any drinks all night, and there was a DJ, a dance floor, and quite a few people for a Monday night. A sign at the entrance informed the patrons that there was an extra charge for spilling drinks on the floor or for throwing up. We did not stay long enough to see if anybody was charged extra that night.

It was only in the last night that we had some dignified drinking. We went to a small, nice place called Bistrot near the Taipower Building stop of the subway, which I highly recommend to any other theoretician who should happen to visit Taipei. They had a very wide selection of beers, including, amazingly, Chimay, which was served in a proper Chimay glass. They also had Hoegaarden, and pretty much anything you can name.

Kekou Kele?

One day, I drank soda with lunch in Taipei.

The other side of the bottle is more familiar.

The chinese label reads 可口可樂: in pinyin that's ke kou ke le. The 'ou' is pronounced 'o' (for example, the common name Zhou is pronounced like "Joe") and a final 'e' sounds similar enough to the 'a' in "cola," so the Chinese name sounds sort of "caco cala." Why isn't the Chinese name 口可口樂? Apparently, the other name sounds better.

When looking for the Chinese name of a foreign brand, it is common to privilege the "niceness" of the name over the phonetic faithfulness. Google's Chinese name is 谷歌, which is gu ge in pinyin and it means something like "song of the valley." Perhaps what they did was to privilege phonetics, instead. (There is, by the way, an online petition to ask Google to change its Chinese name.)

This also came up when, in Beijing, it was decided that I should get a Chinese name. I suggested something that would sound like lǔ kà or lú kà. Apparently, however, either there are no such characters, or they would not sound nice. So far, the best we have come up with is 路卡, which is pronounced lù kǎ and is pretty good phonetically. The two characters mean "road" and "block," respectively, so together they could mean "road-block," which is a good name for a professor, except that they are never used together with that meaning. To me, 路课，lù kè, would also sound good: here 课 means "class" (as in "lecture in a course") and 路 means "road." But, I am told, you can't have two 4-th tones in a name. "How are you going to call out a name with two 4-th tones?" Oh well, I hand't thought of that.

See, this Chinese name business is not easy. I know that there are a few Chinese speakers who read this. Any suggestion that is better than 路卡?

Going to STOC and FOCS

With the exception of STOC in Montreal, where I could not go for a visa problem, I have been to every STOC and every FOCS since STOC'97. The official (and historic) purpose of scientific conferences has something to do with the rapid dissemination of research results. In reality, most papers presented at STOC/FOCS had long been disseminated before the conference takes place. There are many other reasons, however, why I like going to these conferences and why I think they are important.

For one thing, they keep our community together. Over time, the scope of theoretical computer science increases, as we become interested in more and more subjects, like error-correcting codes, quantum computing, game theory, and so on. I think it is very important that we have a single place to go to, where results on all these subjects are talked about, and where people can notice connections between what they do and the new things they hear about. Avi has already discussed very eloquently the need to keep in touch with what other theoreticians are doing, so I will refrain from repeating his points. I just want to say: can we have single sessions in STOC too?

This STOC in Seattle had one of the strongest programs among conferences that I can rememeber. There were perhaps four papers each of which would have easily been considered the best paper at some earlier FOCS/STOC. Indeed, the quality of most papers was outstanding.

Most talks were very good too. James Lee says that the reason he goes to talks is that often the speaker will say one sentence that gives some insight that would have been very hard to extract from the paper. That sentence, he says, is what makes the talk worthwhile. He is quite right, and, indeed, someone who went to several talks and who writes often on the web should collect these sentences and put them online. The 20-minutes format helps. It is very hard to prepare such a short talk, but the time constraint puts some pressure to cut to the chase and just say what the paper is about and what new ideas are there in the proof. Among several other talks that I enjoyed (such as Anup Rao's and Irit Dinur's), I liked Guy Kindler's talk on this very technical result. I can't say how well he explained the problem, because I was already familiar with it, but I think his explanation was very clear. With a few minnutes to spare, he started to talk about their very technical proof and he gave an explanation for "why" the result is true that was very clear and that I had not gotten from reading the paper and thinking about related questions.

Normally, another reason why I enjoy going to FOCS/STOC is to see my far-away friends that I get to meet only once in a while, and to catch up with what is new in life and in theory. In this conference, however, I went to talks in almost all the sessions, except when jet lag made me oversleep. (Hence I missed the session on zero knowledge and Russell Impagliazzo's invited talk, which were highly praised by those who attended.) In fact, a few times, there were two talks that I was interested in that were scheduled against each other. Bad parallel sessions, bad, bad, parallel sessions!

By the way, I am aware of a problem here. If there are single sessions then fewer papers can be accepted, and if I thought that almost all papers were so good, how can I support a system that would have led to the rejection of some of them? Well, by now my readers know that coherence is not the strong point of my posts. I don't know, maybe we should have a four-day conference. Or maybe the good rejected papers would be resubmitted to FOCS in Berkeley. Perhaps, by random fluctuations, the quality of the other submittd papers will not be so high, and things will even out.

Which reminds me: people who attended the business meeting at this STOC and at the previous FOCS might have some doubts, but I hear that, yes, there will really be a FOCS'06 in Berkeley.

Not that there is anything wrong with it

Monday, for lunch, six theoreticians head from the STOC conference hotel towards the fish market. It's four Israeli, me, and another non-Israeli. We get our halibut sandwiches and we go sit by the waterfront.

Someone walks by. "Hey, you look Israeli," he says pointing in our general direction, "are you from Israel?" Blank stares from us. "Hey, it's ok if you are," he says as he walks away.

Danshui

On Monday I gave my talk on pseudorandomness and combinatorial constructions, and the whole Taiwanese complexity theory community showed up, all six of them. They are working on my favorite problems, like amplification of hardness, seedless extractors, locally decodable codes, unique games and so on, and we had a good discussion after the talk.

On Tuesday, Chi-Jen took me to see the Palace Museum, that contains Chinese decorative art and calligraphy including extremely old pieces. This is mostly objects that the fleeing Kuomingtan people took with them when they fled from mainland China. Much destruction of art and antiquitities went on during the Cultural Revolution, and so taking these pieces out of the country actually saved them.

Taipei is not a city of architectural wonders, but it has a few beautiful temples. The one I saw is very close to a domestic airport.



I spent the afternoon in Danshui, a pleaant neighborhood by the river.


We got there around 5pm, just when the schoolkids where returning home, and people were coming back from the offices, the night market had just opened, and the place was quite alive. In the middle of all this, someone was practicing calligraphy on the street.


In Danshui, I saw the only funny sign of this trip.

And the thing is, this was for a parking spot in a designated parking area for scooters. The same in Taipei, designated parking areas for scooters have a few spots reserved for the disabled. I have to say, it looks a bit bizarre: a disabled person riding a scooters? Indeed, there are three-wheeled scooters that are driven by people that walk with difficulty. (They are not at all like the small electric ones that are used in America, these ones have regular internal-combustion engines, and they are definitely not meant to be used indoors.)

Finally, this store in Danshui had the most arresting name.

Not the usual place

Sometimes, even in very interesting cities, the club scene offers no surprise. The place closest to my apartment in San Francisco has a dance floor, and two spaces to hang out, each with a bar. On weekends, the dance floor is really crowded, and one can barely move. That is, until you hear

I don't wanna hear, I don't wanna know
Please don't say you're sorry

and then you cannot even move any more.

In Beijing, the place we went to has also two rooms to sit down, two bars, and a crowded dance floor. And then

I've heard it all before
And I can take care of myself

and it gets really crowded.

I was expecting more of the same in Taipei, but I was pleasently surprised. For one thing, the place we went on Friday had only one bar. More significantly, one guy was singing, and a screen was showing some music video. I was afraid we had found Karaoke night, but then the video featured the same guy who was singing. If I got it right he was Fan Ri Chen, a local celebrity. Later the music was a mix of the usual and of Mandarin pop, including Mandarin renderings of famous Western songs. The dance floor was already packed, but then we heard

我在唱什么什么都觉得
原来原来你是我的主打歌

and everybody came to dance. Sorry played, of course, but nobody payed much attention.

Update 5/24/06 YouTube has the video of Ai De Zhu Da Ge (爱的主打歌), the song that I liked. The video is embarassingly bad. They also have a song that Hoeteck likes.

Mother's day in Taipei

On Sunday we briefly hanged out in a shopping district.

A Malaysian singer, "Gary," who is apparently a big Mandarin Pop celebrity was performing on a stage to advertise his latest CD. Seeing at it was Mother's day, he was periodically joined on stage by his mother.

Hoeteck was there before me, and he told me that earlier they had a skit where the mother brought the singer some soup on stage, and then fed him with a spoon.

Being too late in the day to visit any major museum, we moved to the MOCA ("C" is for "contemporary") where, of all things, they had an exhibit of Italian fashion design. We then recamped to a cafe in Ximending, a neighborhood that I would call "yuppie." Locals who are around my age consider it "the place where college students hang out," although college-age folks belittle it as "the place where high-scholl kids go." I was not able to check with any high school student whether this kind of looking-down goes any further. In reality, Ximending has pleasent cafes, nice shops, and a mixed crowd.

Eventually, it was time to move to the Huaxi night market, which is famous for the restaurants that sell snake soup, snake meat, and liquors made partly from snake blood. Each such restaurant has a hawker in front advertising their stuff, and some of them handle a live snake. Every now and then, they feed a hamster to the snake, or even kill and cut open the snake in front of onlookers, but we were not lucky enough to see it. In front of each such restaurant there is a sign, in English and Chinese, that says "no pictures." I was wondering why, and then I noticed another sign that said "none of the snakes served here is a protected species." I did sneak one picture, anyways. These are preserved snakes, or something:

Hoeteck had been looking for Taiwanese eel noodles ever since tasting them in a Taiwanese restaurant in Boston several years ago. Apparently he never found such good eel noodles anywhere else. We found some good eel noodles in Huaxi, but apparently they were not as good as the Bostonian ones.

Rocks, giants, and more dumplings

On Friday Hoeteck gave his well-received and well-attended talk. Later Chi-Jen took us to have dinner at Din Tai Feng, famous for its dumplings. Their specialties are the steamed dumplings called shao long bao, which they make with soup inside. How do you get soup inside the dumpling? (Think about it for a bit, the answer is at the end.) The kitchen is at the center of the restaurant, and it has glass windows all around. The cooks all wear white shirts and surgical masks, and work around a big table. The image of an operating room is very strong. The dinner was great. Later we went to Taipei 101, the "tallest building in the world."

On Saturday, Chi-Jen took us to Yehliu, a seaside town famous for its rocks that have been eroded by the sea into amazing shapes.

Some of them look like mushrooms

This is the "sandal"

And this is the "Egyptian head"

But first, we stopped at a restaurant where we picked our favorite fish and crabs from an aquarium and had them cooked to order. The huge fish, which yielded three different dishes (sashimi, soup and grilled) was surprisingly cheap.

A religious festival of some kind was also going on. The parade included men dressed up as giants.


One can see the head of the person driving the giant showing up in the giant's belly.


There was a market of sort next to the park with the rocks. They were selling snacks such as these. (The ones closer to the camera are wasabi "chips", quite spicy.)


Here is how these flat things are made flat.


There was a lot more being sold in the market.


So, how about the dumplings? The soup is frozen, and a bit of frozen soup is put in the dumpling when it is made. When the dumpling is steamed, the frozen soup melts.

Green men, scooters and dumplings

A city like Taipei is too complex to be "grasped" after just one day. For now, I am happy just noticing little things.

The little green man, for example. At pedestrian crossings, the "walk" signal is, like in most places, a green image of a man. Except that here the image is animated: the little green man walks. What is most entertaining, however, is that when the time is almost up, the image starts flashing (again, like almost everywhere else), and the little green man starts running.

Unlike in Beijing, here they allow portly guys to be security guards. This gentleman, for example, works at the CKS memorial, one of the most important sites in the city.


Like in Rome, scooters are the preferred veichle of transportation here. At rush hour, swarms of scooters engulf the comparatively fewer cars and own the road. Away from rush hour, one sees parked scooters everywhere, in designated parking slots along the streets but also on sidewalks, when space allows. In the picture below, Unidentified Motorist with Red Helmet blocks the view a bit, but it's actually all scooters till the eye can see. (Click on the picture for larger view.)


Unlike in Rome, however, scooters respect traffic law. This means that neither crossing the street as a pedestrian nor riding a scooter as a passenger of a local are death-defying experiences.

Many scooter drivers wear masks (mask as in surgical mask, not Halloween mask) presumably to protect against pollution. In such a style-conscious country, it is unavoidable that a market for designer masks would arise. I have seen women wearing masks with the Burberry's pattern, and even one woman wearing a leopard-dotted jacket and having a matching mask with the same leopard-dots pattern. (By the way, men wear fancy masks too.)

On the important subject of food, yesterday I had street food for the whole day.

For breakfast I had some kind of fried dough wrapped in a flat bread, a bread sandwich, if you will (I didn't do it, but, for best results, you should say "Mmh, fried dough" in the voice of Homer Simpson when you eat it) and an omelette thing also wrapped in flat bread.

Of the various small things we ate for lunch, the dumplings were the highlight. There are, in fact, a few different Chinese terms that all translate into "dumpling" but that are considered to be very different food items. As I was pondering this excessive linguistic specialization, I was told "In Italy, you have dumplings too." "No, no," I had to explain, "not dumplings, we have ravioli that are made from two distinct sheets of dough, you put the fillings on the bottom sheet and then press the other sheet on top. Then there are tortellini, where you use a single sheet of dough and wrap it around the filling. Then there are agnolotti, then ..."

Taipei is a city that does not go to bed early. Lots of people are around in the street on weekdays well past midnight, and, among the many things to do at night, there is a visit to a "night market." Night markets are big outdoor collections of small booths selling various things, mostly clothes and food. They run along small alleys, with booths on either side, and sometimes clothes vendor laying out stuff in the middle, so that one feels very cramped. I mean cramped in a good "look how much is going on all around me" way, not in a bad "will people stop bumping into me" way. Perhaps on weekends it turns into the bad way, I will have to see.

The food at the stalls was better to look at when it was prepared than to eat, but it was not bad. I am just partial to squid: this is before being cooked:


and then while being cooked:

We should see other people

Lance adds more thoughts on the subject of rejection, and he talks about rejection letters. On this subject, Oded had interesting thoughts in an earlier essay. Oded was writing about papers rejected from conferences, but perhaps his point applies more broadly. If I may paraphrase, Oded says that a rejection letter should contain constructive criticism, as appropriate, but it should not explain the reason of the decision. In Oded's view (reiterated in his more recent essay), rejection of papers from conferences and decisions not to hire certain people are simply decisions about the allocation of scarce resources. Typically, they have no sensible rationale, and, in any case, they are not meant to be a judgement on the value of the paper or of the person. It is confusion between allocation decisions and value statements that creates much needless frustration, and it should be avoided.

Offering specific reasons for rejecting a paper or passing on a candidate is then, in Oded's opinion, a step in the wrong direction, because it makes the decision sound indeed more like a value judgement.

Making a job offer is, for a department, a significant long-term commitment, and so it is for a candidate to accept an offer. Deciding where to work greatly affects one's life, and deciding whom to hire has a great effect on a department's life as well. It is no wonder that the comparison to romantic relationships always comes to mind. Indeed, if one thinks of an academic job interview as a blind date set up by common friends, everything makes sense.

So, I was wondering, what does Oded's ideal rejection letter sound like when translated to the setting of romantic relationships? And then it hit me:

It's not you, it's me.

The brutal and savage travel itinerary

Taiwan's president Chen is visiting South America, and, like any wise traveller, he wanted to stop over in New York or San Francisco. Lately, the US has had a strained relationship with president Chen, because of some symbolic pro-independence steps he took, which complicated the relationship between China, Taiwan and US, at a time when international politics is complicated as it is.

So, no New York and no San Francisco for Chen. If he wants, they told him, he can stop over in Alaska. As reported by the BBC:

"They sought brutally and savagely to block the transit stops and foreign trips of our senior officials," Mr Chen said.

"We will not be defeated but will become bolder. The more we are suppressed, the more we will try to walk out," he told the Associated Press.

Now I just hope that my own pro-independence statements won't land me in Alaska too, on my way back from Taipei. I take them all back! Long live the status quo.

What Google thinks of this site

In theory has more than the three or four readers a day that I expected and, interestingly, almost no reader comes from a random web search. (As opposed to, say, a targeted search like "Luca Trevisan in theory".)

The exceptions are interesting, especially because they show what Google thinks that this site is relevant for.

• Some readers were directed here when searching for "P NP", a search for which In Theory is in the top 20.
  
• A few readers came searching for "feminism for dummies", a search for which we are ranked number 3.
  
• Most amusingly, a reader came here searching for "evil masterminds", a sentence that I never wrote. (The power of anchortext and google-bombing.) This is site is ranked number 3 for this search.
  
• Finally, some readers have found this place as the number 1 result for "Beijing stinky tofu".
  

Draw your own conclusions.

p.s. these are the rankings before this entry was posted. Your results may vary.

Bananas prove existence of God

Cosmic Variance reports.

Labor Day

On May 1st, the rest of the world celebrates the Labor Day holyday. In Rome, for example, there is always a big concert in Piazza San Giovanni. This year, the hundreds of thousands of people were in a particular jolly mood. Just a couple of days ago, the new speakers of the House and of the Senate were elected. Fausto Bertinotti, leader of Rifondazione Comunista, is the new speaker of the House. Woo hoo!

A leftist coalition won elections in Italy for the first time in 1996. In 1998, Rifondazione Comunista, already led by Bertinotti, made the government fall in a vote of confidence. Another government was sort of put together, but then the coalition lost the 2001 elections, as expected. At the time, I resolved I would never, ever vote for that party (I had not, in 1996, and did not in 2001) until Bertinotti would step down. I am not, however, good with resolutions. Lately, Rifondazione has been the only party in Italy to say something leftist about women, civil rights, immigrants, foreign policy, respecting the Constitution, and so on, and I would have voted for them if I had not lost my absentee ballot.

Anyway, here in the US we do not celebrate communist holydays, so yesterday was a day like any other Monday in Berkeley: faculty lunch, teaching about PCP, attending the theory seminar, and so on.

There was, however, something special going on. New immigration regulations are being proposed that, among other things, would make it a felony to assist or shelter an illegal immigrant. This means, for example, that if your boyfriend/girlfriend is an illegal immigrant, and you live together and share the rent etc., then you are liable to a five years sentence in a federal prison. Unless, that is, you report your boyfriend/girlfriend and have him/her deported. Now, what a movie about longing you could get from this story ...

May 1st was a day of strike and protests against these new regulations. The main event in Berkeley was due to start at noon in Sproul plaza. I hanged out there around 11:30. There was a group performing a traditional native central-American dance, and a big crowd all around.

Inevitably, an older white man with a long beard (the type we affectionately call "aging hippie") came with a Palestinian flag. This mixing of messages is very Bay Area. During Critical Mass, the event on the last Friday of each month when large groups of bicyclists take over the streets, many people used to bike with signs that read "No blood for oil," which kind of makes sense, but also "End racism now." Biking against racism? Driving is so white?